package src.CodeTop;

/**
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 *
 * 说明：不允许修改给定的链表。
 *
 * 进阶：
 *
 * 你是否可以使用 O(1) 空间解决此题？
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表节点
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 * 示例 2：
 *
 *
 *
 * 输入：head = [1,2], pos = 0
 * 输出：返回索引为 0 的链表节点
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 * 示例 3：
 *
 *
 *
 * 输入：head = [1], pos = -1
 * 输出：返回 null
 * 解释：链表中没有环。
 */

public class _142LinkedListCycleII {
    public static void main(String[] args) {
        int[] arr = {3, 2, 0, -4};
        ListNode head = TestListNode.generateLinkedList(4, arr);
        // 记录2号结点和-4号结点
        ListNode temp = head;
        ListNode cur = head;
        while (temp.val != 2) {
            temp = temp.next;
        }
        while (cur.val != -4) {
            cur = cur.next;
        }
        // 成环
        cur.next = temp;
        ListNode target = detectCycle(head);
        System.out.println(target.val);
    }

    public static ListNode detectCycle(ListNode head) {
        // 校验合法性
        if (head == null) {
            return null;
        }
        // 标记值，用来标记链表是否有环，默认无环
        boolean flag = false;
        // 定义快慢指针
        ListNode p = head, q = head;
        // 快慢指针遍历链表
        while (p.next != null && q.next != null && q.next.next != null) {
            // 快慢指针后移
            p = p.next;
            q = q.next.next;
            // 若两指针相遇，则证明有环
            if (p == q) {
                // 标记为有环并退出循环
                flag = true;
                break;
            }
        }
        // 如果链表有环
        if (flag) {
            // 将其中一个指针置于头结点处
            p = head;
            // 此时双指针每次只走一步，直到找到环形链表的第一个结点
            while (p != q) {
                p = p.next;
                q = q.next;
            }
            return p;
        }
        // 无环则直接返回
        return null;
    }
}
